package class12;

import class10.TreeTools.*;

/**
 * 你已经学会了树型DP套路了，那么用下面这道题来练练手吧
 * <a href="https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/">1373. 二叉搜索子树的最大键值和</a>
 */
public class ExtraExam {

    int answer = 0;  // 最终结果

    public int maxSumBST(TreeNode root) {
        process(root);
        return answer;
    }

    public static class Info {
        boolean isBST;  // 是否是二叉搜索树
        int sum;  // 该树的总和
        int max;  // 当前树的最大值
        int min;  // 当前树的最小值

        Info(boolean isBST, int sum, int max, int min) {
            this.isBST = isBST;
            this.sum = sum;
            this.max = max;
            this.min = min;
        }
    }

    public Info process(TreeNode root) {
        // base case，当来到空结点的时候，是二叉搜索树，和为0，最大值设为最小值，最小值设为最大值
        if (root == null) {
            return new Info(true, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
        // 去左子树拿信息
        Info left = process(root.left);
        // 去右子树拿信息
        Info right = process(root.right);
        // 下面的if跑的是如果是二叉搜索树，所以这里默认数据要设置为默认不是二叉搜索树的时候
        Info result = new Info(false, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
        // 满足四种条件，则记录下答案
        if (left.isBST && right.isBST && root.value > left.max && root.value < right.min) {
            result.isBST = true;
            result.max = Math.max(root.value, right.max);
            result.min = Math.min(root.value, left.min);
            result.sum = left.sum + right.sum + root.value;
            answer = Math.max(answer, result.sum);
        }
        return result;
    }

}
